package tree

import (
	"math"
)

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
	return helper1(root, math.MinInt64, math.MaxInt64)
}

func helper1(root *TreeNode, lower, upper int) bool {
	if root == nil {
		return true
	}
	if lower >= root.Val || upper <= root.Val {
		return false
	}
	return helper1(root.Left, lower, root.Val) && helper1(root.Right, root.Val, upper)
}

// 二叉搜索树中序遍历，则序列一定是升序的
func isValidBST1(root *TreeNode) bool {
	stack := make([]*TreeNode, 0)
	inOrder := math.MinInt64
	for len(stack) > 0 || root != nil {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}
		root := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if inOrder >= root.Val {
			return false
		}
		// 记录中序遍历时前一个节点的值，二叉搜索树中序遍历一定是一个递增的序列，所以前一个节点的值一定小于后一个节点
		inOrder = root.Val
		root = root.Right
	}
	return true
}

// 中序遍历
func InOrder(root *TreeNode) []int {
	result := make([]int, 0)
	stack := make([]*TreeNode, 0)
	for len(stack) > 0 || root != nil {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}
		root := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		result = append(result, root.Val)
		root = root.Right
	}
	return result
}
